The present invention relates to a variable-length code (VLC) decoder.
In order to reduce the bandwidth of a communication means or the capacity of a storage medium in transmitting or recording a moving picture, the picture is compressed and encoded. International standards for moving picture encoding include H.261, MPEG (moving picture experts group) 1, MPEG2, and so on.
These encoding methods are combinations of motion vector estimation and motion compensation, DCT (discrete cosine transform), quantization, zigzag scanning, variable-length coding, etc. Variable-length coding is an encoding method for reducing the average number of bits by converting quantized fixed-length codewords into a bit stream of variable-length codewords according to their statistics. To decode such a bit stream and present moving pictures, it is necessary to perform variable-length code (VLC) decoding for converting the variable-length codewords into the original fixed-length data. In VLC decoding, the codewords have non-constant lengths, and it is not possible to identify the first bit position of each variable-length codeword in the bit stream. Therefore, the codewords need to be decoded according to the order of bits included in the bit stream.
Various VLC decoders have been proposed in the art to realize a high-speed VLC decoding operation. A known VLC decoder is disclosed in U.S. Pat. No. 5,245,338. FIG. 11 is a block diagram illustrating a VLC decoder of this type. The VLC decoder shown in FIG. 11 decodes variable-length codewords with a maximum code length of 16 bits.
A buffer 901 stores an input bit stream. If a read signal RD is xe2x80x9c1xe2x80x9d, the buffer 901 outputs the stored bit stream to a first barrel shifter 911 and a first input register 912 on a 16-bit basis in the next cycle. The buffer 901 holds the output for one cycle.
The first and second input registers 912 and 913 have a 16-bit configuration, and latch the input data in the next cycle if an update signal is xe2x80x9c1xe2x80x9d.
The first barrel shifter 911 combines the outputs of the second and first input registers 913 and 912 and the output of the buffer 901 with each other as the upper, middle and lower 16-bit sub-sequences, respectively, to obtain a 48-bit data sequence. Then, using a sum SM (from 0 through 31), i.e., the output of an adder 914, as a shift length (from 1 through 32), the first barrel shifter 911 selects 16 bits from the 48-bit combined data sequence and then writes the 16-bit data sequence on a first barrel shifter register 922. The 16 bits selected are the (shift length+1)th through (shift length+16 bits of the 48-bit data sequence as counted from the most significant bit (MSB) thereof. It should be noted that the xe2x80x9cfirst bitxe2x80x9d herein means the MSB of the 48-bit combined data sequence.
A second barrel shifter 921 combines the outputs of second and first barrel shifter registers 923 and 922 with each other as the upper and lower 16-bit sub-sequences, respectively, to obtain a 32-bit data sequence. Then, using the output of a shift length register 925 as a shift length (from 1 through 16), the second barrel shifter 921 selects 16 bits from the 32-bit combined data sequence and then writes the 16-bit data sequence on the second barrel shifter register 923. The 16 bits selected are the (shift length+1)th through (shift length+16)th bits of the 32-bit data sequence as counted from the MSB thereof.
A lookup table (LUT) 924 performs variable-length code decoding on the output of the second barrel shifter 921 to obtain a decoded symbol DC and a code length CL (from 1 through 16), and then writes the code length CL on the shift length register 925. The LUT 924 is a table so compiled as to output a decoded symbol and a code length for each codeword with any of various lengths. The LUT 924 receives each codeword with the first bit thereof regarded as the MSB thereof.
The adder 914 adds together the output of the shift length register 925 (from 1 through 16) and the output of an accumulation register 915 (from 0 through 15) to output the sum SM. The adder 914 writes a carry signal CR, which is xe2x80x9c1xe2x80x9d if the sum SM is 16 to 31, on a hold register 916 and writes a remainder RM (from 0 through 15) of the sum SM modulo 16 on the accumulation register 915. Thus, the MSB of the 5-bit sum SM, obtained by adding together the 5-bit output of the shift length register 925 and the 4-bit output of the accumulation register 915, is the carry signal CR, while the remaining 4 bits thereof is the remainder RM of the sum SM modulo 16. The carry signal CR is used as an update signal for the first and second input registers 912 and 913, and the read signal RD, i.e., the output of the hold register 916, is used as a read signal for the buffer 901.
FIG. 12 illustrates exemplary cycle-by-cycle data flows in the VLC decoder shown in FIG. 11. For example, xe2x80x9ca1-a8xe2x80x9d denotes an 8-bit data sequence consisting of a1, a2, a3, a4, a5, a6, a7 and a8. For example, xe2x80x9ca1-a8b1-b6c1-c2xe2x80x9d for the buffer output in cycle 0 denotes a 16-bit data sequence consisting of a1 through a8, b1 through b6 and c1 through c2.
In FIG. 12, as for cycle 0 to cycle 2, the update and read signals and shift lengths for the first and second barrel shifters are xe2x80x9c1xe2x80x9d, xe2x80x9c1xe2x80x9d, xe2x80x9c16xe2x80x9d and xe2x80x9c16xe2x80x9d, respectively, to set initial-state data for the respective registers. From cycle 3 on, the same processing is repeatedly performed based on the respective values of the carry and read signals, the accumulation register and the shift length register.
In this manner, a decoded symbol is obtained every cycle. At the beginning of the decoding operation, the first decoded output is obtained in cycle 2, i.e., two cycles later than cycle 0 at which the input buffer 901 outputs data for the first time.
However, the known VLC decoder as illustrated in FIG. 11 needs two input registers and a 48-bit-input, 16-bit-output circuit as the first barrel shifter. Thus, the decoder must be implemented at a large circuit size, and occupies an excessively broad chip area when realized as an LSI.
In addition, when the conventional VLC decoder illustrated in FIG. 11 starts its decoding operation, it is not until two cycles have passed after the input buffer has supplied its first output that a first decoded codeword is obtained. If multiple streams of variable-length codewords are included in a single bit stream, information other than the variable-length code, such as headers, is included between the variable-length codeword streams. In such a case, the variable-length codeword streams are not contiguous with each other, and the VLC decoding cannot be performed continuously. Thus, if the VLC decoding cannot be performed consecutively, the 2-cycle delay occurs every time a variable-length codeword stream starts to be decoded. As a result, it takes a huge number of cycles to decode the entire bit stream.
It is therefore an object of the present invention to implement a variable-length code decoder at a reduced circuit size so that the decoder occupies a smaller chip area and supplies its decoded output at a much smaller delay.
Specifically, an inventive variable-length code decoder sequentially decodes a series of variable-length codewords included in a bit stream and outputs decoded symbols corresponding to the codewords. The decoder includes an interface section and a decoding section. The interface section accumutates various code lengths of the decoded codewords to obtain a sum. In accordance with the sum, the interface section selects a contiguous data sequence having a length of N bits (where N is a maximum code length of the variable-length codewords) from another contiguous data sequence, which has a length of 2N or 2Nxe2x88x921 bits and included in the bit stream, and outputs the N-bit contiguous data sequence. The decoding section receives the output of the interface section and decodes a codeword, included in a combination of the output and a previous output of the interface section, by reference to a lookup table, thereby obtaining and outputting a decoded symbol and also outputting a code length of the decoded codeword to the interface section.
According to this invention, the decoder is implementable in a smaller circuit size, because the interface section selects an N-bit contiguous data sequence, needed for the decoding section, from a 2N- or (2Nxe2x88x921)-bit contiguous data sequence included in the bit stream.
In one embodiment of the present invention, the interface section may include accumulation register, adder, input register and barrel shifter. The accumulation register stores and outputs a remainder derived from the sum. The adder adds together the code length and the remainder, which have been output from the decoding section and the accumulation register, respectively, to obtain the sum. Then, the adder outputs a quotient and a remainder, which are obtained by dividing the sum by N, as a carry signal and a new remainder, respectively. The input register stores and outputs a contiguous data sequence, which has a length of N or Nxe2x88x921 bits and is included in the bit stream, if the carry signal is one. The barrel shifter combines the output of the input register with the following N-bit contiguous data sequence, which is included in the bit stream, so that the bits are arranged in the same order as in the bit stream. Next, the barrel shifter selects an N-bit contiguous data sequence from the combined data sequence using the remainder, output from the accumulation register, as a shift input value, and then outputs the N-bit contiguous data sequence selected to the decoding section. The N-bit contiguous data sequence selected starts from a bit position that has been determined in accordance with the shift input value.
According to this embodiment, the carry signal is used for updating the data stored on the input register, and the remainder of the sum is written on the accumulation register. Accordingly, the remainder will be used as a shift length for the barrel shifter one cycle later. Thus, even if the sum of code lengths exceeds the maximum code length so that a shift operation should be performed at a shift length exceeding the maximum code length, the barrel shifter may perform a shift operation at a small shift length. This is because by updating the input register, after the barrel shifter has performed a first shift operation at the shift length equal to the maximum code length, the shifter may perform another shift operation at the remaining shift length in the next cycle. Therefore, the bit width of the barrel shifter can be reduced. Moreover, since only one input register is required, only one cycle is needed for initialization.
In this particular embodiment, the barrel shifter preferably selects and outputs the N-bit contiguous data sequence, which starts from an (M+2)th bit (where M is the shift input value) of the combined data sequence as counted from the first bit thereof.
According to this embodiment, the interface section can select and output the N-bit contiguous data sequence, needed for the decoding section, in accordance with the shift input value.
In another embodiment of the present invention, the decoding section may includes barrel shifter, barrel shifter register and lookup table. The barrel shifter combines outputs of the barrel shifter register and the interface section so that the bits are arranged in the same order as in the bit stream. Next, the barrel shifter selects an N-bit contiguous data sequence from the combined output using the code length, output from the lookup table, as a shift input value, and then outputs the N-bit contiguous data sequence selected. The N-bit contiguous data sequence selected starts from a bit position that has been determined in accordance with the shift input value. The barrel shifter register stores and outputs the output of the barrel shifter. And the lookup table outputs the symbol, corresponding to the codeword included in the output of the barrel shifter register, and outputs the code length of the decoded codeword.
According to such an embodiment, the output of the interface section is directly input to the barrel shifter of the decoding section, and the output of the barrel shifter is written on the barrel shifter register. Accordingly, the decoder may have a reduced number of barrel shifter registers.
In this particular embodiment, the barrel shifter preferably selects and outputs the N-bit contiguous data sequence, which starts from an (L+1)th bit (where L is the shift input value) of the combined output as counted from the first bit thereof.
According to this embodiment, an N-bit contiguous data sequence, beginning with a codeword to be decoded next, can be input to the lookup table.
In still another embodiment, the decoding section may further include a code length converter for outputting a value obtained by subtracting one from the code length. The barrel shifter may select and output the N-bit contiguous data sequence, which starts from an (L+2)th bit of the combined output as counted from the first bit thereof, by using not the code length but the output of the code length converter as the shift input value.
According to this embodiment, the range of shift input values for the barrel shifter can be narrowed. Particularly, if the maximum code length is an nth power of two, the number of bits representing the shift input value decreases. Thus, the shift input for the barrel shifter can have a smaller bit width.
In yet another embodiment, the decoding section may include barrel shifter, first and second barrel shifter registers, lookup table and shift length register. The barrel shifter combines outputs of the first and second barrel shifter registers with each other so that the bits are arranged in the same order as in the bit stream. Next, the barrel shifter selects an N-bit contiguous data sequence from the combined output using a value, derived from an output of the shift length register, as a shift input value, and then outputs the N-bit contiguous data sequence selected. The N-bit contiguous data sequence selected starts from a bit position that has been determined in accordance with the shift input value. The first barrel shifter register stores and outputs the output of the interface section. The second barrel shifter register stores and outputs the output of the barrel shifter. The lookup table outputs the decoded symbol, corresponding to the codeword included in the output of the barrel shifter, and outputs the code length of the decoded codeword. And the shift length register stores and outputs a value corresponding to the code length.
According to this embodiment, an N-bit contiguous data sequence, including a variable-length codeword to be decoded, can be selected from the output of the interface section, and then decoded sequentially.
In this particular embodiment, the shift length register preferably stores and outputs the code length. The barrel shifter preferably selects and outputs the N-bit contiguous data sequence, which starts from an (L+1)th bit of the combined output as counted from the first bit thereof, by using the output of the shift length register as the shift input value.
According to this embodiment, an N-bit contiguous data sequence, beginning with a codeword to be decoded next, can be input to the lookup table.
In an alternative embodiment, the decoding section may further include a code length converter for outputting a value obtained by subtracting one from the code length. The barrel shifter may select and output the N-bit contiguous data sequence, which starts from an (L+2)th bit of the combined output as counted from the first bit thereof, by using the code-length-minus-one value, which has been input thereto by way of the code length converter and the shift length register, as the shift input value.
According to this embodiment, the range of shift input values for the barrel shifter can be narrowed. Particularly, if the maximum code length is an nth power of two, the number of bits representing the shift input value decreases. Thus, the shift input for the barrel shifter can have a smaller bit width.
In still another embodiment, the inventive variable-length code decoder may include, in combination: the interface section including the accumulation register, adder, input register and barrel shifter; and the decoding section including the barrel shifter, barrel shifter register and lookup table.
According to such an embodiment, the output of the barrel shifter of the interface section is directly input to the barrel shifter of the decoding section, and the output of the latter barrel shifter is written on the barrel shifter register. Accordingly, the decoder may have a reduced number of barrel shifter registers.
In an alternative embodiment, the inventive variable-length code decoder may include, in combination: the interface section including the accumulation register, adder, input register and barrel shifter; and the decoding section including the barrel shifter, first and second barrel shifter registers, lookup table and shift length register.
According to this embodiment, an N-bit contiguous data sequence, including a variable-length codeword to be decoded, can be selected from the output of the barrel shifter of the interface section, and then decoded sequentially.
In the decoder according to one of these two embodiments, the adder preferably obtains the sum by adding one to the sum of the code length and the remainder that have been output from the decoding section and the accumulation register, respectively. And the lookup table preferably outputs, as the code length, a value obtained by subtracting one from the code length of the codeword.
According to this embodiment, the range of shift input values for the barrel shifter can be narrowed. Particularly, if the maximum code length is an nth power of two, the number of bits representing the shift input value decreases. Thus, the shift input for the barrel shifter can have a smaller bit width. Also, there is no need to provide any code length converter.